1. Field of the Invention
The present invention relates to a memory cache (or cache memory) unit and such a system which are capable of, when a CPU accesses a main memory unit, preventing the low access speed of the main memory unit from causing an overhead, and thus, improving its performance.
Particularly, the present invention relates to a cache for a data memory which stores data. More specifically, it relates to a cache for a so-called stack memory, or a data memory in which addresses are consecutively accessed (i.e., data are read from or written in consecutive addresses) by push-pop instructions.
2. Description of the Related Art
Aiming at reducing the time necessary for execution of push-pop instructions and avoiding holding unnecessary data in a cache after the push-pop, the following stack-cache control method and stack cache have been known conventionally. For example, a microcomputer system including a microcomputer executes data processing by supporting a stack structure in which the data inputted last is first outputted as a data structure in a main memory unit, and by distinguishing the input of data in a stack as a push and the output of data from the stack as a pop, from the other data writing/read-out. In the control method of this system, when the microcomputer pushes, the cache memory holds a set of the corresponding address and data instead of the main memory unit. Then, the hold data which has not been pushed into the main memory unit is pushed into the main memory unit by the microcomputer at a suitable time while its access is not being given to the outside. When the microcomputer pops, if the corresponding data is held, the data is outputted to the microcomputer from the cache memory instead of the main memory unit. Then, the microcomputer pops it from the main memory unit at a suitable time while its access is not being given to the outside, so that the data which has become unnecessary as a result of the microcomputer's pop is replaced with the data at the bottom part of the stack which may be popped later (e.g., refer to Patent Document 1).
Herein, Patent Document 1 is Japanese Patent Laid-Open No. 5-143330 specification.
However, the above described conventional stack-cache system and stack-cache control method do not differ at all from generally-used methods for heightening the speed of memory access based on random access to a data memory. In other words, they could not make good use of the feature of regular access which a stack memory has. This has presented a disadvantage in that it is difficult to execute processing at higher speed.
This disadvantage becomes serious, especially, in a memory system which uses the stack access to a great extent, such as a Java (which is a registered trademark) system. In recent years, the needs of the Java system or the like have become greater, especially for ubiquitous computing or the like. Specific disadvantages will be described below.
(First Disadvantage)
For example, let's assume that the push of data into a stack has been executed in the direction where memory addresses increase in the main memory unit. In addition, this stack is assumed to be cached in a cache memory. Then, a cache miss is assumed to have been made by the push of data A. On this condition, the contents of one cache-unit of new data memory from the memory address in which the cache miss has taken place are read into the cache memory from the main memory unit.
This state is shown in FIG. 35. FIG. 35 shows that a stack pointer 913 is at the memory area of an address 90, and the data A is kept pushed in the memory area of the address 90. At this time, as shown in FIG. 35, the push of the data A allows the stack pointer 913 to move from the memory area of an address 89 to the memory area of the address 90.
As shown in FIG. 35, the memory area of addresses 90, 91, 92 and 93 is one cache-unit. As the memory area of the address 90 of this cache-unit has been accessed, this cache-unit made up of the memory area of the addresses 90, 91, 92 and 93 is read into the cache memory from the main memory unit.
However, the following data push will write on top of, and thus delete, the contents of this cache-unit of new data memory read into the cache memory, according to the regularity of stack access. In other words, the contents are the data which will not be read out at all. Reading such data never to be read out into the cache memory from the main memory unit has a harmful effect on the realization of speedier memory access.
(Second Disadvantage)
Oppositely from the above description, let's assume that the pop of data from a stack has been executed in the direction where memory addresses decrease in the main memory unit. In addition, this stack is assumed to be cached in a cache memory. Then, a cache miss is assumed to have been made by the pop h of data B. On this condition, the contents of one cache-unit of data memory from a larger memory address than the memory address in which the cache miss has taken place are written back to the cache memory from the main memory unit.
This state is shown in FIG. 36. As shown in FIG. 36, the pop of the data B allows a stack pointer 923 to move from the memory area of the address 90 to the memory area of the address 89. As shown in FIG. 36, the memory area of the addresses 90, 91, 92 and 93 is one cache-unit. As the stack pointer 923 has moved to the memory area of the address 89 other than this cache-unit, this cache-unit made up of the memory area of the addresses 90, 91, 92 and 93 is written back to the main memory unit from the cache memory. Thus, the cache memory is opened.
However, the contents of this cache-unit of data memory written back to the main memory unit, according to the regularity of stack access is the contents which have been read out by the already-executed data pop. They will not be read out again at all. Writing back such data never to be read out to the main memory unit from the cache memory has a harmful effect on the realization of speedier memory access.
(Third Disadvantage)
Furthermore, let's assume that the push of data into a stack has been executed in the direction where memory addresses increase in the main memory unit. In addition, this stack is assumed to be cached in a cache memory. Then, the pushes of data C, D, . . . , E have been consecutively executed. On this condition, in the memory area of lower addresses than the address indicated with a stack pointer which is the area where a push-pop is currently executed in the stack, many pieces of stack-pushed data are stored, i.e., C or D in this example. It is not highly probable that these pieces of data stored in the memory area of lower addresses will be read out by a pop for a while.
This state is shown in FIG. 37. FIG. 37 shows that a stack pointer 933 is at the memory area of an address 194, and the data C, D, . . . , E is kept consecutively pushed, for example, from the memory area of an address 80 way below, up to this memory area of the address 194. As shown in FIG. 37, one cache-unit from the address 80 up to the address 83 usually keeps occupying its cache memory area unless the cache memory becomes full, so that it cannot written back to the main memory unit. Then, the cache-unit is only written back to the main memory unit to vacate the cache memory for another memory area, when the cache memory has been filled up.
Thus, after the cache memory has become zero and a demand for a new cache memory area has been made, write-back is executed. This has a harmful effect on the realization of speedier memory access.
For example, as shown in FIG. 37, the memory area way below the memory area of the address 194 in the present position of the stack pointer 933, for example, the memory area of addresses 80 to 83, will not highly probably be read out by a pop for the present. Therefore, different from the prior art disclosed in Patent Document 1, for example, the contents of one cache-unit of cache memory which is the memory area of the addresses 80 to 83 can be written back beforehand to the main memory unit, as a means of resolving the above described disadvantage. This could make the speed of memory access higher than in the case where, when a cache memory has almost been filled up, the contents of the cache memory are written in a rush into the main memory unit so that its empty space can be created.
(Fourth Disadvantage)
Moreover, let's assume that the pop of data from a stack has been executed in the direction where memory addresses decrease in the main memory unit. In addition, this stack is assumed to be cached in a cache memory. Then, the pops of data F, G, . . . , H have been consecutively executed.
On this condition, the data which is stack-pushed into the address area which has lower values than the address indicated with a stack pointer which is the area where a push-pop is currently executed in the stack, for example, into the memory area of addresses 84 to 87 in this example, will highly probably be read out consecutively soon by a pop.
This state is shown in FIG. 38. FIG. 38 shows that a stack pointer 943 is at the memory area of an address 91, and the data F, G, . . . , H is kept consecutively popped, for example, from the memory area of an address 196 way above, up to this memory area of the address 91. As shown in FIG. 38, one cache-unit from the address 84 up to the address 87 cannot usually be read into the cache memory area from the main memory unit, unless a memory which belongs to this area, for example, the memory area of the address 87, is accessed by the execution of a pop. Then, for example, the cache-unit is only read into the cache memory from the main memory unit, when the memory area of this address 87 has been accessed by the execution of a pop.
Thus, the area which belongs to the new cache memory unit is accessed for the first time, and a demand is made for the data which corresponds to the new cache memory area. Thereafter, the data is read into the cache memory area from the main memory unit. This has a harmful effect on the realization of speedier memory access.
For example, as shown in FIG. 38, the cache-unit which occupies the memory area right below the memory area of the address 91 in the present position of the stack pointer 943, for example, the memory area of the addresses 84 to 87, will highly probably be read out consecutively soon by a pop. Therefore, different from the prior art disclosed in Patent Document 1, for example, one cache-unit of data which is the memory area of the addresses 84 to 87 can be read into the cache memory area from the main memory unit, as a means of resolving the above described disadvantage. This could make the speed of memory access higher than in the case where, when access has been executed to the memory area which is not in the cache memory, the contents of the main memory unit are read in a rush into the cache memory.